package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhenzicheng
 * @date 2022-06-28 11:51
 */
public class BinaryTreeZigzagLevelOrderTraversal_103 {

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    travel(root, result, 0);

    return result;
  }

  private void travel(TreeNode root, List<List<Integer>> result, int height) {
    if (root == null) return;

    // 新的一层子list
    if (height >= result.size()) {
      result.add(new ArrayList<>());
    }
    // 拿到刚刚新增的那一层
    List<Integer> curLevel = result.get(height);

    if (height % 2 == 0) {
      curLevel.add(root.val);
    } else {
      curLevel.add(0, root.val);
    }

    travel(root.left, result, height + 1); // 递归左节点
    travel(root.right, result, height + 1); // 递归右节点
  }
}
